package simple.array;

/**
 * <a href="https://leetcode.cn/problems/degree-of-an-array/">697. 数组的度</a>
 * 给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
 * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 * 示例 1：
 *   输入：nums = [1,2,2,3,1]
 *   输出：2
 *   解释：
 *     输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
 *     连续子数组里面拥有相同度的有如下所示：
 *     [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
 *     最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
 * 示例 2：
 *   输入：nums = [1,2,2,3,1,4,2]
 *   输出：6
 *   解释：
 *     数组的度是 3 ，因为元素 2 重复出现 3 次。
 *     所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
 * 提示：
 *   nums.length 在 1 到 50,000 范围内。
 *   nums[i] 是一个在 0 到 49,999 范围内的整数。
 * @author 刘学松
 * @date 2023-06-20 8:43
 */
public class 数组的度 {
    public int findShortestSubArray(int[] nums) {
        // 找最大最小值
        int min = 50000,max = 0;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int[] count = new int[max - min + 1];
        // 统计
        int maxLength = 0;
        for (int num : nums) {
            maxLength = Math.max(maxLength, ++count[num - min]);
        }
        if (maxLength == 1) {
            return 1;
        }
        // 找最短
        int minLength = 50000;
        for (int i = 0; i < count.length; i++) {
            if (count[i] == maxLength) {
                int num = min + i;
                int left = 0, right = nums.length - 1;
                while (left < right && nums[left] != num) {
                    ++left;
                }
                while (left < right && nums[right] != num) {
                    --right;
                }
                minLength = Math.min(minLength, right - left);
            }
        }
        return minLength + 1;
    }
}
